package com.example.javamaday.leetcode;

import com.example.javamaday.leetcode.base.ListNode;

// 排序链表 （插入法）
public class LeetCodeTest0147 {

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        new LeetCodeTest0147().sortList(head);
    }


    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dumpy = new ListNode(Integer.MIN_VALUE);
        ListNode current = head;
        while (current != null) {
            ListNode tempNode = dumpy;
            while (tempNode != null) {
                if (tempNode.next == null) {
                    ListNode currentNext = current.next;
                    current.next = null;
                    tempNode.next = current;
                    current = currentNext;
                    break;
                } else {
                    if (tempNode.next.val < current.val) {
                        tempNode = tempNode.next;
                    } else {
                        ListNode tempNext = tempNode.next;
                        ListNode currentNext = current.next;
                        current.next = tempNext;
                        tempNode.next = current;
                        current = currentNext;
                        break;
                    }
                }
            }
        }
        return dumpy.next;
    }


}
